package xyz.scootaloo.oj.leetcode

import org.junit.Test

/**
 * dfs
 * @author flutterdash@qq.com
 * @since 2021/4/7 23:33
 */
class P200 {

    private fun numIslands(grid: Array<CharArray>): Int {
        val row = grid.size
        val column = grid[0].size
        fun dfs(r: Int, c: Int) {
            if (r < 0 || r >= row || c < 0 || c >= column)
                return
            if (grid[r][c] == '0')
                return
            grid[r][c] = '0'
            dfs(r + 1, c) // down
            dfs(r - 1, c) // up
            dfs(r, c + 1) // right
            dfs(r, c - 1) // left
        }

        var isLandCount = 0
        for (r in 0 until row) {
            for (c in 0 until column) {
                if (grid[r][c] == '1') {
                    dfs(r, c)
                    isLandCount++
                }
            }
        }
        return isLandCount
    }

    @Test
    fun test0() {
        val input1 = arrayOf(
            charArrayOf('1', '1', '1', '1', '0'),
            charArrayOf('1', '1', '0', '1', '0'),
            charArrayOf('1', '1', '0', '0', '0'),
            charArrayOf('0', '0', '0', '0', '0'),
        )
        val input2 = arrayOf(
            charArrayOf('1', '1', '0', '0', '0'),
            charArrayOf('1', '1', '0', '0', '0'),
            charArrayOf('0', '0', '1', '0', '0'),
            charArrayOf('0', '0', '0', '1', '1'),
        )
        println(numIslands(input1))
        println(numIslands(input2))
    }

}
